#include "double_list.h"
//创建双向链表
pNode CreateList()
{
	int i,length=0,data=0;
	//分配初始内存
	pNode  pHead=(pNode)malloc(sizeof(Node));
	if(NULL==pHead){
		printf("malloc for pHead failed!\n");
		exit(-1);
		}
	pHead->LPN=-1;
	pHead->isD=-1;
	pHead->cold=-1;
	pHead->Pre=pHead;
	pHead->Next=pHead;
	
	return pHead;
	}

//初始化两个队列的头部和长度
void InitDoubleList()
{
    HotHead=CreateList();
    HotLength=0;
    ColdHead=CreateList();
    ColdLength=0;
}

//初始化相应的配置参数
void InitVariable()
{
    buf_size=1024*4;
    Min_lc=0.2*buf_size;
    //后续的统计变量
    buffer_cnt=0;
    buffer_hit=0;
    buffer_miss=0;
    buffer_read_hit=0;
    buffer_read_miss=0;
    buffer_write_hit=0;
    buffer_write_miss=0;
    //无力读写次数
    physical_read=0;
    physical_write=0;
}

void resetCacheStat()
{
    cache_read_num=0;
    cache_write_num=0;
}

//释放两个队列
void DestoryDouleList()
{
    FreeList(&HotHead);
    HotLength=0;
    FreeList(&ColdHead);
    ColdLength=0;
}

	//判断链表是否为空
int IsEmptyList(pNode pHead)
{
    pNode pt=pHead->Next;
    if(pt==pHead)
    {
        return 1;
    }else
    {
        return 0;
    }
}
//返回链表的长度
int GetListLength(pNode pHead)
{
    int length=0;
    pNode pt=pHead->Next;
    while (pt !=pHead)
    {
        length++;
        pt=pt->Next;
    }
    return length;
}

//输出打印链表
void PrintList(pNode pHead)
{
    pNode pt=pHead->Next;
    printf("the list is follow:\n");
    while(pt!=pHead)
    {
        printf("the LPN is %d\t",pt->LPN);
        printf("the cold is %d\t",pt->cold);
        printf("the isD is %d\n",pt->isD);
        pt=pt->Next;
    }
}

//从链表中插入节点,这里之后有读写操作的operation
int InsertEleList(pNode pHead,int pos,int LPN,int operation)
{
    pNode pt=NULL,p_new=NULL;
    pt=pHead->Next;
    if(pos>0&&pos<GetListLength(pHead)+2)
    {
        p_new=(pNode)malloc(sizeof(Node));
        if(NULL==p_new)
        {
            printf("malloc for New Node!\n");
            exit(-1);
        }

        while(1)
        {
            pos--;
            if(0==pos)
                break;
            pt=pt->Next;
        }
        //新建节点
        p_new->LPN=LPN;
        if(operation==0)
            p_new->isD=1;
        else
            p_new->isD=0;
        //第一次插入的节点默认是非cold
        p_new->cold=0;
        //这里的双链表是首位相接的，也就是head前面就是最后一个节点
        //插入pt的前面
        p_new->Pre=pt->Pre;
        p_new->Next=pt;
        //衔接
        pt->Pre->Next=p_new;
        pt->Pre=p_new;
        return 1;
    }else {
        return  0;
    }
}

//向链表中删除节点
int DeleteEleList(pNode pHead,int pos)
{
    pNode pt=pHead,ps=NULL;
    //pos=0就是pHead
    if(pos>0&&pos<GetListLength(pHead)+1){
        while(1)
        {
            pos--;
            if(pos==0)
                break;
            pt=pt->Next;
        }
        //此时的pt是pos的前一个节点
        //ps才是要删除的节点位置
        ps=pt->Next;
        pt->Next=ps->Next;
        ps->Next->Pre=pt;
        //释放ps指向的节点
        free(ps);
        return 1;
    }else{
        printf("delete pos %d is error\n",pos);
        return 0;
    }

}

//删除链表的尾部的数据
int DelLRUList(pNode pHead)
{
    pNode pt=pHead->Pre;
    if(pt==pHead){
        printf("List is empty！！\n");
        exit(-1);
    }
    //将尾部衔接
    pt->Pre->Next=pHead;
    pHead->Pre=pt->Pre;
    //释放删除点pt的内存
    free(pt);
    return 1;
}

//删除整个链表，释放内存

void FreeList(pNode *ppHead)
{
    pNode pt=NULL;
    while(*ppHead!=NULL){
        pt=(*ppHead)->Next;
        free(*ppHead);
        if(NULL!=pt)
            pt->Pre=NULL;
        *ppHead=pt;
    }
}

//从链表中找到特定的LPN值，并返回节点的指针位置,如果不存在返回NULL
pNode FindLPNinList(pNode pHead,int LPN)
{
    pNode ps=NULL,pt=pHead->Next;
    int count=0;
    while(pt!=pHead)
    {
        count++;
        if(pt->LPN==LPN){
            ps=pt;
            ps->cold=0;
            break;
        }
        pt=pt->Next;
    }
    //调试输出语句遍历循环了多少次
//    printf("the while count is %d\n",count);
    return ps;
}

//将命中的数据移动到MRU位置,因为节点的类型一样，所以改函数的复用没问题
//都是移动到Hot-list的MRU位置
int MoveToHotMRU(pNode HHead,pNode HitNode)
{
    pNode pt=NULL,ps=NULL;
    //删除cold-list中的命中节点
    HitNode->cold=0;
    pt=HitNode->Pre;
    pt->Next=HitNode->Next;
    HitNode->Next->Pre=pt;
    //插入到hot-list队列中的MRU位置
    ps=HHead->Next;
    ps->Pre=HitNode;
    HHead->Next=HitNode;
    HitNode->Next=ps;
    HitNode->Pre=HHead;

    //更改对应的队列长度,服用存在问题，命中的可能是hot-list的队列
    ColdLength=GetListLength(ColdHead);
    HotLength=GetListLength(HotHead);
    //错误判断
    if(ColdLength!=GetListLength(ColdHead)||HotLength!=GetListLength(HotHead))
    {
        printf("Move To Hot MRU exist error\n");
        printf("ColdLength is %d\t the length of Cold-list is %d\n",ColdLength,GetListLength(ColdHead));
        printf("HotLength is %d\t the length of hot-list is %d\n",HotLength,GetListLength(HotHead));
        exit(-1);
    }
    return 1;
}


//找到剔除项AD-LRU的二次机会，返回的是要剔除的项的指针,优先提出干净页
pNode FindVicitmList(pNode pHead)
{
    pNode Victim=pHead->Pre,pt=NULL,ps=NULL;
    int count=0,L;
    int flag=0;
    L=GetListLength(pHead);
    //debug test
    if(IsEmptyList(pHead)!=0){
        printf("the list is empty!\n");
        exit(-1);
    }
    //debug test
    //先遍历寻找队列中尾部的干净页优先提出
    ps=pHead->Pre;
    while(ps!=pHead)
    {
        if(ps->isD==0){
            Victim=ps;
            //找到干净页则不用下面遍历寻找脏页剔除了
            flag=1;
            break;
        }
        //向前继续搜索干净页
        ps=ps->Pre;
    }
    //如果找不到干净页才循环遍历脏页剔除
    if (0 == flag) {
        while (Victim->cold != 1) {
            pt = Victim;
            Victim = Victim->Pre;
            pt->cold = 1;
            //之前的Victim移动到Head后面
            pt->Pre = pHead;
            pt->Next = pHead->Next;
            pHead->Next->Pre = pt;
            pHead->Next = pt;
            //衔接新的尾部
            pHead->Pre = Victim;
            Victim->Next = pHead;
            //debug
            count++;
            if (count > L + 2) {
                printf("exist error in while\n");
                break;
            }
            //debug
        }
        //test for debug脏页提出一定最后是尾部的LRU
        if (Victim != pHead->Pre) {
            printf("this operation exist error\n");
            exit(-1);
        }
    }
    return Victim;
}

//找到buffer中是否存在改LPN，存在返回改LPN的对应节点的指针,无论命中那个都是要移动到Hot-List的MRU
pNode FindLPNInBuffer(int LPN,int operation)
{
    pNode pt=NULL;
    pt=FindLPNinList(HotHead,LPN);
    if(pt==NULL)
    {
        pt=FindLPNinList(ColdHead,LPN);
    }
    //遍历结束
    if(pt!=NULL){
        //判断命中的类型
        buffer_hit++;
        pt->cold=0;
        if(operation==0){
            pt->isD=1;
            buffer_write_hit++;
            cache_write_num++;
        } else{
            buffer_read_hit++;
            cache_read_num++;
        }
    }else{
        buffer_miss++;
        if(operation==0){
            buffer_write_miss++;
        }else{
            buffer_read_miss++;
        }
    }
    return pt;
}

//添加新的数据到cold
void AddNewToCold(int LPN,int operation)
{
    InsertEleList(ColdHead,1,LPN,operation);
    ColdLength++;
    physical_read++;
    //debug test
    if(GetListLength(ColdHead)!=ColdLength){
        printf("the add new to cold list exist error\n");
        printf("the ColdLength is %d\t the Length of Cold-list is %d\n",ColdLength,GetListLength(ColdHead));
        exit(-1);
    }
}

//删除链表中的对应的数据页项
int DelEleList(pNode pHead,pNode Victim)
{
    //首先做一个错误检测，判断相应的队列是否存在该Victim
    int flag=0;
    pNode pt=pHead->Pre;
    while(pt!=pHead){
        //找到对应的剔除选项
        if(pt==Victim)
        {
            flag=1;
            break;
        }
        pt=pt->Pre;
    }
    if(flag==0){
        printf("链表中不存在删除的数据项\n");
        exit(1);
    }
    //如果上述的检测都满足，则开始直接删除
    pt=Victim->Pre;
    //删除节点前后之间建立新的链接关系
    pt->Next=Victim->Next;
    Victim->Next->Pre=pt;
    //释放对应的节点
    free(Victim);
    return 0;
}


//删除操作,选择合适的队列剔除操作，根据min_lc
void ExcludeVicitm()
{
    pNode Victim=NULL;
    //错误判断
    if(ColdLength!=GetListLength(ColdHead)||HotLength!=GetListLength(HotHead))
    {
        printf("Exclude Vicitm function error\n");
        printf("ColdLength is %d\t the length of Cold-list is %d\n",ColdLength,GetListLength(ColdHead));
        printf("HotLength is %d\t the length of hot-list is %d\n",HotLength,GetListLength(HotHead));
        exit(1);
    }

    if(ColdLength>Min_lc){
        //选择cold-list剔除
        Victim=FindVicitmList(ColdHead);
        if(Victim==NULL){
            printf("Find VicitmList exist error\n");
            exit(-1);
        }
        //判断剔除的Vicitm是否为脏
        if(Victim->isD==1){
            physical_write++;
        }
        //剔除尾部的数据
//        DelLRUList(ColdHead);
//        不再是单纯的剔除尾部的数据页了，还存在中间的干净页剔除的操作
        DelEleList(ColdHead,Victim);
        ColdLength--;
        //debug
        if(ColdLength!=GetListLength(ColdHead)){
            printf("Del LRU in Cold-List exist error\n");
            printf("ColdLength is %d\t the length of Cold-list is %d\n",ColdLength,GetListLength(ColdHead));
            exit(-1);
        }
    }else{
        Victim=FindVicitmList(HotHead);
        if(Victim==NULL){
            printf("Find VicitmList exist error\n");
            exit(-1);
        }
        if(Victim->isD==1){
            physical_write++;
        }
        //剔除尾部的数据
//        DelLRUList(HotHead);
        DelEleList(HotHead,Victim);
        HotLength--;
        //debug
        if(HotLength!=GetListLength(HotHead)){
            printf("Del LRU in Hot-List exist error\n");
            printf("HotLength is %d\t the length of hot-list is %d\n",HotLength,GetListLength(HotHead));
            exit(-1);
        }
    }
}

double ComputeCacheDelay()
{
    double delay=0.0;
    double cache_read_delay=0.0;
    double cache_write_delay=0.0;
    cache_read_delay=(double)cache_read_num*(double)CACHE_READ_DELAY;
    cache_write_delay=(double)cache_write_num*(double)CACHE_WRITE_DELAY;
    delay=cache_read_delay+cache_write_delay;
    resetCacheStat();
    return delay;
}

double CacheManage(int secno,int scount,int operation )
{

    pNode pt=NULL;
    int LPN,LPNCount;
    double cache_delay=0.0;
    LPN=secno/SEC_PRE_PAGE;
    LPNCount=(secno+scount-1)/SEC_PRE_PAGE-(secno)/SEC_PRE_PAGE+1;
    resetCacheStat();
    while(LPNCount>0) {
        buffer_cnt++;
        pt = FindLPNInBuffer(LPN, operation);
        if (pt != NULL) {
            //命中移动到Hot-list队列中
            MoveToHotMRU(HotHead, pt);
        } else {
            if (ColdLength + HotLength >= buf_size) {
                //如果队列满了就要选择剔除
                ExcludeVicitm();
            }
            //添加新的数据到cold
            AddNewToCold(LPN, operation);
        }
        LPNCount--;
        LPN++;
    }
    cache_delay=ComputeCacheDelay();
//    PrintList(HotHead);
//    PrintList(ColdHead);
    //test print
    printf("the secno is %d\t the scount is %d\t the operation is %d\t cache_delay is %f\n",secno,scount,operation,cache_delay);
    return cache_delay;
}

//PrintStatResult
void PrintBufferStat()
{
    double hit_rate;
    hit_rate=(double)buffer_hit/buffer_cnt;
    printf("all page request is %d\t hit rate is %f\n",buffer_cnt,hit_rate);
    printf("the physical read count is %d\t physical write count is %d\n",physical_read,physical_write);
}